Classic pathfinding algorithms like Dijkstra's Algorithm and A* are used to generate travel routes in applications such as video games, mobile robotics, and architectural design. Despite the popularity of these algorithms, the paths they produce rarely go straight. In this article, you'll learn how to compute highly direct paths using a counting technique inspired by Pascal's Triangle. It's an idea my colleagues and I developed and recently published in the Journal of Artificial Intelligence Research [1]. With the simple step of counting paths, you can overcome a long-standing problem with traditional pathfinding.

Counting the number of shortest paths on a grid is a simple procedure with close ties to Pascal's triangle. We show how path counting can be used to select relatively direct grid paths for AI-related applications involving navigation through spatial environments. Typical implementations of Dijkstra's algorithm and A* prioritize grid moves in an arbitrary manner, producing paths which stray conspicuously far from line-of-sight trajectories. We find that by counting the number of paths which traverse each vertex, then selecting the vertices with the highest counts, one obtains a path that is reasonably direct in practice and can be improved by refining the grid resolution. Central Dijkstra and Central A* are introduced as the basic methods for computing these central grid paths. Theoretical analysis reveals that the proposed grid-based navigation approach is related to an existing grid-based visibility approach, and establishes that central grid paths converge on clear sightlines as the grid spacing approaches zero. A more general property, that central paths converge on direct paths, is formulated as a conjecture.

Video-game designers often tessellate continuous 2-dimensional terrain into a grid of blocked and unblocked square cells. The three main ways to calculate short paths on such a grid are to determine truly shortest paths, shortest vertex paths and shortest grid paths, listed here in decreasing order of computation time and increasing order of resulting path length. We show that, for both vertex and grid paths on both 4-neighbor and 8-neighbor grids, placing vertices at cell corners rather than at cell centers tends to result in shorter paths. We quantify the advantage of cell corners over cell centers theoretically with tight worst-case bounds on the ratios of path lengths, and empirically on a large set of benchmark test cases. We also quantify the advantage of 8-neighbor grids over 4-neighbor grids.

Video-game designers often tessellate continuous 2-dimensional terrain into a grid of blocked and unblocked square cells. The three main ways to calculate short paths on such a grid are to determine truly shortest paths, shortest vertex paths and shortest grid paths, listed here in decreasing  order of computation time and increasing order of resulting path length. We show that, for both vertex and grid paths on both 4-neighbor and 8-neighbor grids, placing vertices at cell corners rather than at cell centers tends to result in shorter paths. We quantify the advantage of cell corners over cell centers theoretically with tight worst-case bounds on the ratios of path lengths, and empirically on a large set of benchmark test cases. We also quantify the advantage of 8-neighbor grids over 4-neighbor grids.

There has been much interest recently in problems that com-bine high-level task planning with low-level motion planning.In this paper, we present a problem of this kind that arises inmulti-vehicle mission planning. It tightly integrates task al-location and scheduling, who will do what when, with pathplanning, how each task will actually be performed. It ex-tends classical vehicle routing in that the cost of executing aset of high-level tasks can vary significantly in time and costaccording to the low-level paths selected. It extends classi-cal motion planning in that each path must minimize costwhile also respecting temporal constraints, including thoseimposed by the agent’s other tasks and the tasks assigned toother agents. Furthermore, the problem is a subtask withinan interactive system and therefore must operate within se-vere time constraints. We present an approach to the problembased on a combination of tabu search, linear programming,and heuristic search. We evaluate our planner on represen-tative problem instances and find that its performance meetsthe demanding requirements of our application. These resultsdemonstrate how integrating multiple diverse techniques cansuccessfully solve challenging real-world planning problemsthat are beyond the reach of any single method.